package leetcode_100;

/**
 *@author 周杨
 *JumpGame_55 Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
             jump length is 0, which makes it impossible to reach the last index.
 *describe:  1.回溯超时
 *			 2.O(N)时间复杂度的算法 用max哨兵记录当前能到的最远位置 如果最远位置超出 则返回true
 *								否则判断每个坐标点的能到的最远位置 更新哨兵 如果当前最远位置就是目前这个位置  则返回false
 *           AC 92%
 *2018年5月7日 下午2:32:55
 */
public class JumpGame_55 {
	int nums[];
	int n;
	public static void main(String[] args) {
		JumpGame_55 test=new JumpGame_55();
		System.out.println(test.canJump1(new int[] {0}));

	}
	
	public boolean canJump(int[] nums) {
		if(nums.length==0)
			return false;
        this.nums=nums;
        this.n=nums.length;
		return help(0);
    }

	public boolean help(int index) {
		if(index>=this.n-1)
			return true;
		if(this.nums[index]==0)
			return false;
		for(int i=nums[index];i>0;--i) {
			boolean res=help(index+i);
			if(res)
				return true;
		}
		return false;
	}
	
	public boolean canJump1(int []nums) {
        this.nums=nums;
        this.n=nums.length;
        int max=0;//记录当前能跳到的最大值
        for(int i=0;i<n;++i) {
        	int count=i+nums[i];
        	max=max>count?max:count;
        	if(max>=this.n-1)
        		return true;
        	if(max<i+1)
        		return false;
        }
        return false;      	
	}
}
